class ListNode {
    constructor(val) {
      this.val = val;
      this.next = null;
    }
  }
  
  function mergeSort(head) {
    if (!head || !head.next) return head; // 递归终止条件
  
    let mid = getMiddle(head);
    let right = mid.next;
    mid.next = null; // 断开链表
  
    let leftSorted = mergeSort(head);
    let rightSorted = mergeSort(right);
  
    return merge(leftSorted, rightSorted);
  }
  
  function getMiddle(head) {
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }
  
  function merge(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
  
    while (l1 && l2) {
      if (l1.val < l2.val) {
        current.next = l1;
        l1 = l1.next;
      } else {
        current.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }
  
    current.next = l1 ? l1 : l2;
    return dummy.next;
  }
  
  function fn(arr) {
    if (!arr.length) return null;
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
      current.next = new ListNode(arr[i]);
      current = current.next;
    }
    return mergeSort(head);
  }
  
  // 测试
  let sortedList = fn([1, 3, 2, 4, 5]);
  let result = [];
  while (sortedList) {
    result.push(sortedList.val);
    sortedList = sortedList.next;
  }
  console.log(result);
  